package day02

// day02
//
// 647. 回文子串
//
// https://leetcode.cn/problems/palindromic-substrings/
//
// ```go
func countSubstrings(s string) int {
	n := len(s)
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	ans := 0
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if s[i] == s[j] {
				if j-i <= 1 {
					dp[i][j] = true
					ans++
				} else {
					if dp[i+1][j-1] {
						dp[i][j] = true
						ans++
					}
				}
			}
		}
	}
	return ans
}

//```

// 516. 最长回文子序列
//
// https://leetcode.cn/problems/longest-palindromic-subsequence/
//
// ```go
func longestPalindromeSubseq(s string) int {
	n := len(s)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := range dp {
		dp[i][i] = 1
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1] + 2
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-1])
			}
		}
	}
	return dp[0][n-1]
}

//```

// 739. 每日温度
//
// https://leetcode.cn/problems/daily-temperatures/
//
// ```go
func dailyTemperatures(temperatures []int) []int {
	stack := make([]int, 0)
	ans := make([]int, len(temperatures))
	for i := range temperatures {
		val := temperatures[i]
		if len(stack) > 0 {
			for len(stack) > 0 {
				topIdx := stack[len(stack)-1]
				if val > temperatures[topIdx] {
					cnt := i - topIdx
					ans[topIdx] = cnt
					stack = stack[:len(stack)-1]
				} else {
					break
				}
			}
		}
		stack = append(stack, i)
	}
	return ans
}

//```
